package com.example.javabasic.suanfa.jiandan.快排;

/**
 * @description 快速排序
 * @Author Lin FuYuan
 * @date 2021/5/7
 */
public class QuiteSort {

    //首先根据传入数组大小定义两个栈

    public static void main(String[] args) {
        int[] n ={5,6,2,1,7,8,9,3,1,3,0,5};
        stackSort(n, 0, n.length-1);
        for (int i = 0; i <n.length ; i++) {
            System.out.print(n[i]+" ");
        }
    }

    public static void stackSort(int[] arr,int i ,int j){
        //如果 i 和j 相等 , 那么说明排序结束  返回结果
        if(i>j){
            return ;
        }
        //获取第一个数为基准数
        int low = i;
        int high = j;
        int n = arr[low];
        while(low <high){
            //先从右往左找小于基准数n的下标, 右侧大  左侧小
            while(low<high && arr[high] >= n ){
                high--;
            }
            //再从左往右找大于 基准数n的下标, 右侧大  左侧小
            while(low<high && arr[low] <= n){
                low++;
            }
            //如果 low <high 则进行交换
            if(low <high){
                int w = arr[low];
                arr[low] = arr[high];
                arr[high] = w;
            }
        }
        //将基准位与最后 low 和high相遇的位置交换
        arr[i] = arr[low];
        arr[low] = n;
        //交换完后 递归 进行下一轮交换
        stackSort(arr,i,low-1);
        stackSort(arr,low+1,j);
        return;

    }

}
